package com.gupao.alg.alg34;

/**
 * 实现这三个方法
 * uniquePathsByRecursion()
 * uniquePaths2DimensionArray()
 * uniquePathsByDpArray()
 */
public class Topic_2_2_FindPaths {
    public static void main(String[] args) {
        int m = 3, n = 3;
        System.out.println("通过递归实现：");
        System.out.println(uniquePathsByRecursion(m, n));

        System.out.println("通过二维数组实现：");
        System.out.println(uniquePaths2DimensionArray(m, n));

        System.out.println("通过动态数组实现：");
        System.out.println(uniquePathsByDpArray(m, n));
    }

    /**
     * 方法1 通过递归方式实现
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePathsByRecursion(int m, int n) {
        if(m==1&&n==2||m==2&&n==1){
            return 1;
        }
        if(m==1&&n>1){
            return uniquePathsByRecursion(m,n-1);
        }
        if(n==1&&m>1){
            return uniquePathsByRecursion(m-1,n);
        }
        if(n>1&&m>1){
            return uniquePathsByRecursion(m-1,n)+uniquePathsByRecursion(m,n-1);
        }

        return 0;

    }

    public static int search(int m, int n) {
        return 0;
    }

    /**
     * 通过二维数组实现
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePaths2DimensionArray(int m, int n) {

        int[][] tables = new int[m][n];
        for(int i=0;i<m;i++){
            tables[i][0] = 1;
        }
        for(int j=0;j<n;j++){
            tables[0][j] = 1;
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                tables[i][j] = tables[i-1][j] + tables[i][j-1];
            }
        }
        return tables[m-1][n-1];
    }

    /**
     * 通过动态数组实现
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePathsByDpArray(int m, int n) {
        return 0;
    }
}
